package com.zlk.algorithm.algorithm.sort;

/**
 * @program: algorithm
 * @ClassName CountSort
 * @description: 计数排序  	时间O(N)		空间O(Max)		稳定性有（每个桶里面都是队列先进先出）
 * 对数据范围要求严格，比如人类年龄，规模可以限定为0-200
 * @author: slfang
 * @create: 2024-01-29 13:24
 * @Version 1.0
 **/
public class CountSort {


    /**
     * only for 0~200 value
     * @param arr
     */
    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }
}
